package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 124. 二叉树中的最大路径和
 * @date 2025/3/14 12:41
 */
public class E124 {

    private int max = Integer.MIN_VALUE;

    @SuppressWarnings("all")
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    /**
     * 递归求解，参考max depth方法
     * @param root 二叉树的根节点
     * @return 当前子树的最大深度，如果深度小于0，则返回0,但是要考虑root.val
     */
    private int dfs(TreeNode root) {
        if(root == null) return 0;
        // 递归求解左右子树最大深度，如果深度小于0，则返回0
        int left = Math.max(dfs(root.left), 0);
        int right = Math.max(dfs(root.right), 0);
        max = Math.max(max, left + right + root.val);
        return Math.max(left, right) + root.val;
    }
}
